<!DOCTYPE html>
<html  lang="en">
<head>
    <meta charset="utf-8">
<title>图解算法 - noback</title>
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" />



    <meta name="description" content="这个博文可能跟图解算法的内容讲的不一样，一般都是看了书之后换一种自己认为更加形象的比喻去理解内容，如果想要看图解算法的可以去购买或者查找一些PDF的书籍，笔记对于算法和数据结构并不像语言那样，对于版本的更迭有一定程度的影响。另外，算法图解这本书中的实例都是依靠Python编写的。 二分查找其实二分法在我们生活中已经出现过了很多次，比如玩一个猜价格游戏，规定价格在500-1000之内，如果我们一个一">
<meta property="og:type" content="article">
<meta property="og:title" content="图解算法">
<meta property="og:url" content="http://alpaca-h.gitee.io/2019/12/29/blog_back_new/%E6%89%A9%E5%B1%95/%E5%9B%BE%E8%A7%A3%E7%AE%97%E6%B3%95/index.html">
<meta property="og:site_name" content="noback">
<meta property="og:description" content="这个博文可能跟图解算法的内容讲的不一样，一般都是看了书之后换一种自己认为更加形象的比喻去理解内容，如果想要看图解算法的可以去购买或者查找一些PDF的书籍，笔记对于算法和数据结构并不像语言那样，对于版本的更迭有一定程度的影响。另外，算法图解这本书中的实例都是依靠Python编写的。 二分查找其实二分法在我们生活中已经出现过了很多次，比如玩一个猜价格游戏，规定价格在500-1000之内，如果我们一个一">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="http://alpaca-h.gitee.io/images/og_image.png">
<meta property="article:published_time" content="2019-12-29T05:07:36.000Z">
<meta property="article:modified_time" content="2019-12-29T05:14:23.407Z">
<meta property="article:author" content="Alpaca">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://alpaca-h.gitee.io/images/og_image.png">







<link rel="icon" href="/images/favicon.svg">


<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/bulma@0.7.2/css/bulma.css">
<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.4.1/css/all.css">
<link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Ubuntu:400,600|Source+Code+Pro">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/highlight.js@9.12.0/styles/androidstudio.css">


    
    
    
    <style>body>.footer,body>.navbar,body>.section{opacity:0}</style>
    

    
    
    
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/lightgallery@1.6.8/dist/css/lightgallery.min.css">
    <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/justifiedGallery@3.7.0/dist/css/justifiedGallery.min.css">
    

    
    

<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/outdatedbrowser@1.1.5/outdatedbrowser/outdatedbrowser.min.css">


    
    
    
    

<link rel="stylesheet" href="/css/back-to-top.css">


    
    

    
    
    
    

    
    
<link rel="stylesheet" href="/css/progressbar.css">
<script src="https://cdn.jsdelivr.net/npm/pace-js@1.0.2/pace.min.js"></script>

    
    
    

    
    
    
        <script async="" src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script>
    

    


<link rel="stylesheet" href="/css/style.css">
<meta name="generator" content="Hexo 4.2.0"><link rel="alternate" href="/atom.xml" title="noback" type="application/atom+xml">
</head>
<body class="is-3-column">
    <nav class="navbar navbar-main">
    <div class="container">
        <div class="navbar-brand is-flex-center">
            <a class="navbar-item navbar-logo" href="/">
            
                <img src="/images/logo.svg" alt="图解算法" height="28">
            
            </a>
        </div>
        <div class="navbar-menu">
            
            <div class="navbar-start">
                
                <a class="navbar-item"
                href="/">Home</a>
                
                <a class="navbar-item"
                href="/archives/">Archives</a>
                
                <a class="navbar-item"
                href="/categories/">Categories</a>
                
                <a class="navbar-item"
                href="/tags/">Tags</a>
                
                <a class="navbar-item"
                href="/about/">About</a>
                
            </div>
            
            <div class="navbar-end">
                
                    
                    
                    <a class="navbar-item" target="_blank" title="AlphaLxy GitHub" href="https://www.github.com/AlphaLxy">
                        
                        <i class="fab fa-github"></i>
                        
                    </a>
                    
                
                
                <a class="navbar-item is-hidden-tablet catalogue" title="Catalogue" href="javascript:;">
                    <i class="fas fa-list-ul"></i>
                </a>
                
                
                <a class="navbar-item search" title="Search" href="javascript:;">
                    <i class="fas fa-search"></i>
                </a>
                
            </div>
        </div>
    </div>
</nav>
    
    <section class="section">
        <div class="container">
            <div class="columns">
                <div class="column is-8-tablet is-8-desktop is-9-widescreen has-order-2 column-main"><div class="card">
    
    <div class="card-content article ">
        <h1 class="title is-size-3 is-size-4-mobile has-text-weight-normal">
            
                <i class="fas fa-angle-double-right"></i>图解算法
            
        </h1>
        
        <div class="level article-meta is-size-7 is-uppercase is-mobile is-overflow-x-auto">
            <div class="level-left">
                <time class="level-item has-text-grey" datetime="2019-12-29T05:07:36.000Z"><i class="far fa-calendar-alt">&nbsp;</i>2019-12-29</time>
                
                <time class="level-item has-text-grey is-hidden-mobile" datetime="2019-12-29T05:14:23.407Z"><i class="far fa-calendar-check">&nbsp;</i>2019-12-29</time>
                
                
                <div class="level-item">
                <i class="far fa-folder-open has-text-grey"></i>&nbsp;
                <a class="has-link-grey -link" href="/categories/blog-back-new/">blog_back_new</a>&nbsp;/&nbsp;<a class="has-link-grey -link" href="/categories/blog-back-new/%E6%89%A9%E5%B1%95/">扩展</a>
                </div>
                
                
                <span class="level-item has-text-grey">
                    <i class="far fa-clock"></i>&nbsp;
                    
                    
                    5 minutes read (About 715 words)
                </span>
                
                
                <span class="level-item has-text-grey" id="busuanzi_container_page_pv">
                    <i class="far fa-eye"></i>
                    <span id="busuanzi_value_page_pv">0</span> visits
                </span>
                
            </div>
        </div>
        
        <div class="content">
            <p>这个博文可能跟图解算法的内容讲的不一样，一般都是看了书之后换一种自己认为更加形象的比喻去理解内容，如果想要看图解算法的可以去购买或者查找一些PDF的书籍，笔记对于算法和数据结构并不像语言那样，对于版本的更迭有一定程度的影响。另外，算法图解这本书中的实例都是依靠Python编写的。</p>
<h2 id="二分查找"><a href="#二分查找" class="headerlink" title="二分查找"></a>二分查找</h2><p>其实二分法在我们生活中已经出现过了很多次，比如玩一个猜价格游戏，规定价格在500-1000之内，如果我们一个一个的去猜，则需要猜1000-500-2次，但是使用二分法猜测价格时，即每次对半猜测价格，那么每次都可以减去一半的错误价格，就像一张白纸对半折一样，最后的区域则会越来越小。而使用的次数则是log2n步。<br>同样的例子也存在于字典中，查字典的手法同样也可以使用二分法。</p>
<p><strong>概念:最多需要猜测的次数与列表长度相同，这被称为线性时间</strong></p>
<h3 id="例子1"><a href="#例子1" class="headerlink" title="例子1"></a>例子1</h3><p>创建一个函数，接受一个有序数组和一个元素，如果指定的元素出现在数组中，则返回其位置</p>
<pre><code class="bash">def filter_number(list,keywords):
    for i in range(len(list)):
        if list[i] == keywords:
            print(i)
if __name__ == &quot;__main__&quot;:
    list = [1,2,4,5,343,67,86,656]    
    keywords = 343
    filter_number(list,keywords)</code></pre>
<p>如上所示是普通的遍历方法，遍历5次后得到343这个参数。但如果匹配的数字是656，则需要匹配7次，如果数组的长度是1000,匹配的结果是最后一个，则需要匹配1000次，这样就增加了负担</p>
<pre><code class="bash"># 二分查找匹配
def filter_number(list,keywords):
    first = 0
    end = len(list) - 1

    while first &lt;= end:
        mid = int((first+end) / 2)
        guess = list[mid]
        if guess == keywords:
            return mid
        elif guess &lt; keywords:
            first = mid + 1
        elif guess &gt; keywords:
            end = mid - 1
    return None 

if __name__ == &quot;__main__&quot;:
    list = [1,2,4,5,6,8,9,10,11]    
    keywords = 8
    index = filter_number(list,keywords)
    print(index)</code></pre>
<p>如上则完成了需求,<strong>但是二分查找存在一个问题，则是如果列表不是按照顺序排列的，那么二分法就存在的意义就不大了，因为当你使用二分法得到中间值时，你只能判断中间值与题目给出的元素之间大小，而中间值的附近元素，并不是依次递增或是递减的</strong></p>
<h3 id="练习"><a href="#练习" class="headerlink" title="练习"></a>练习</h3><p>假设有一个包含128个名字的有序列表，你要使用二分查找在其中查找一个名字，请 问最多需要几步才能找到<br>2的7次等于128  所以是7次<br>上面列表的长度翻倍后，最多需要几步？<br>8次</p>

        </div>
        
            <ul class="post-copyright">
            <li><strong>本文标题：</strong><a href="http://alpaca-h.gitee.io/2019/12/29/blog_back_new/%E6%89%A9%E5%B1%95/%E5%9B%BE%E8%A7%A3%E7%AE%97%E6%B3%95/">图解算法</a></li>
            <li><strong>本文作者：</strong><a href="http://alpaca-h.gitee.io">Alpaca</a></li>
            <li><strong>本文链接：</strong><a href="http://alpaca-h.gitee.io/2019/12/29/blog_back_new/%E6%89%A9%E5%B1%95/%E5%9B%BE%E8%A7%A3%E7%AE%97%E6%B3%95/">http://alpaca-h.gitee.io/2019/12/29/blog_back_new/%E6%89%A9%E5%B1%95/%E5%9B%BE%E8%A7%A3%E7%AE%97%E6%B3%95/</a></li>
            <li><strong>发布时间：</strong>2019-12-29</li>
            <li><strong>版权声明：</strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh" rel="external nofollow" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明出处！
            </li>
            </ul>
        
        
        
        
    </div>
</div>





<div class="card card-transparent">
    <div class="level post-navigation is-flex-wrap is-mobile">
        
        <div class="level-start">
            <a class="level level-item has-link-grey  article-nav-prev" href="/2019/12/29/blog_back_new/%E6%89%A9%E5%B1%95/linux%E5%B0%B1%E8%AF%A5%E8%BF%99%E4%B9%88%E5%AD%A6%E7%AC%94%E8%AE%B0/">
                <i class="level-item fas fa-chevron-left"></i>
                <span class="level-item">linux就该这么学</span>
            </a>
        </div>
        
        
        <div class="level-end">
            <a class="level level-item has-link-grey  article-nav-next" href="/2019/12/29/blog_back_new/%E6%89%A9%E5%B1%95/%E9%A2%9D%E5%A4%96%E7%9F%A5%E8%AF%86/">
                <span class="level-item">额外知识</span>
                <i class="level-item fas fa-chevron-right"></i>
            </a>
        </div>
        
    </div>
</div>



</div>
                




<div class="column is-4-tablet is-4-desktop is-3-widescreen  has-order-1 column-left ">
    
        
<div class="card widget">
    <div class="card-content">
        <nav class="level" style="margin-bottom:1rem">
            <div class="level-item has-text-centered">
                <div>
                    
                        <img class="image is-96x96 has-mb-6" src="https://www.gravatar.com/avatar/e0f4032c0f2d1068ffffbaf93c0bef52?s=96" alt="Xinyu Liu">
                    
                    
                    <p class="is-size-4 is-block">
                        Xinyu Liu
                    </p>
                    
                    
                    <p class="is-size-6 is-block">
                        Alpha Lxy
                    </p>
                    
                    
                    <p class="is-size-6 is-flex is-flex-center has-text-grey">
                        <i class="fas fa-map-marker-alt has-mr-7"></i>
                        <span>Beijing, China</span>
                    </p>
                    
                </div>
            </div>
        </nav>
        <nav class="level menu-list is-mobile" style="margin-bottom:1rem">
            <div class="level-item has-text-centered is-marginless">
                <a href="/archives/">
                    <p class="heading">
                        Posts
                    </p>
                    <p class="title has-text-weight-normal">
                        40
                    </p>
                </a>
            </div>
            <div class="level-item has-text-centered is-marginless">
                <a href="/categories/">
                    <p class="heading">
                        Categories
                    </p>
                    <p class="title has-text-weight-normal">
                        13
                    </p>
                </a>
            </div>
            <div class="level-item has-text-centered is-marginless">
                <a href="/tags/">
                    <p class="heading">
                        Tags
                    </p>
                    <p class="title has-text-weight-normal">
                        0
                    </p>
                </a>
            </div>
        </nav>
        <div class="level">
            <a class="level-item button is-link is-rounded" href="https://www.github.com/AlphaLxy" target="_blank">
                <i class="fab fa-github"></i>&nbsp;&nbsp;Follow</a>
        </div>
        
        
    </div>
</div>

    
        
<div class="card widget column-left is-sticky" id="toc">
    <div class="card-content">
        <div class="menu">
            <h3 class="menu-label">
                Catalogue
            </h3>
            <ul class="menu-list"><li>
        <a class="is-flex" href="#二分查找">
        <span class="has-mr-6">1</span>
        <span>二分查找</span>
        </a><ul class="menu-list"><li>
        <a class="is-flex" href="#例子1">
        <span class="has-mr-6">1.1</span>
        <span>例子1</span>
        </a></li><li>
        <a class="is-flex" href="#练习">
        <span class="has-mr-6">1.2</span>
        <span>练习</span>
        </a></li></ul></li></ul>
        </div>
    </div>
</div>


    
    
        <div class="column-right-shadow is-hidden-widescreen ">
        
        </div>
    
</div>

                
            </div>
        </div>
    </section>
    <footer class="footer">
    <div class="container">
        <div class="level">
            <div class="level-start has-text-centered-mobile">
                <a class="footer-logo is-block has-mb-6" href="/">
                
                    <img src="/images/logo.svg" alt="图解算法" height="28">
                
                </a>
                <p class="is-size-7">
                &copy; 2020 Alpaca&nbsp;
                Powered by <a href="http://hexo.io/" target="_blank">Hexo</a> & <a
                        href="http://github.com/ppoffice/hexo-theme-icarus" target="_blank">Icarus</a>
                
                <br>
                <span id="busuanzi_container_site_uv">
                Visited by <span id="busuanzi_value_site_uv">0</span> users
                </span>
                
                </p>
            </div>
            <div class="level-end">
            
                <div class="field has-addons is-flex-center-mobile has-mt-5-mobile is-flex-wrap is-flex-middle">
                
                
                <p class="control">
                    <a class="button is-white is-large" target="_blank" title="CC BY-NC-SA 4.0" href="https://creativecommons.org/licenses/by-nc-sa/4.0/">
                        
                        <i class="fab fa-creative-commons"></i>&nbsp;<i class="fab fa-creative-commons-by"></i>&nbsp;<i class="fab fa-creative-commons-nc"></i>&nbsp;<i class="fab fa-creative-commons-sa"></i>&nbsp;
                        
                    </a>
                </p>
                
                <p class="control">
                    <a class="button is-white is-large" target="_blank" title="AlphaLxy GitHub" href="https://www.github.com/AlphaLxy">
                        
                        <i class="fab fa-github"></i>&nbsp;
                        
                    </a>
                </p>
                
                </div>
            
            </div>
        </div>
    </div>
</footer>

    <script src="https://cdn.jsdelivr.net/npm/jquery@3.3.1/dist/jquery.min.js"></script>
<script src="https://cdn.jsdelivr.net/npm/moment@2.22.2/min/moment-with-locales.min.js"></script>
<script>moment.locale("en");</script>


    
    
    
    <script src="/js/animation.js"></script>
    

    
    
    
    <script src="https://cdn.jsdelivr.net/npm/lightgallery@1.6.8/dist/js/lightgallery.min.js" defer></script>
    <script src="https://cdn.jsdelivr.net/npm/justifiedGallery@3.7.0/dist/js/jquery.justifiedGallery.min.js" defer></script>
    <script src="/js/gallery.js" defer></script>
    

    
    

<div id="outdated">
    <h6>Your browser is out-of-date!</h6>
    <p>Update your browser to view this website correctly. <a id="btnUpdateBrowser" href="http://outdatedbrowser.com/" target="_blank" rel="noopener">Update
            my browser now </a></p>
    <p class="last"><a href="#" id="btnCloseUpdateBrowser" title="Close">&times;</a></p>
</div>
<script src="https://cdn.jsdelivr.net/npm/outdatedbrowser@1.1.5/outdatedbrowser/outdatedbrowser.min.js" defer></script>
<script>
    document.addEventListener("DOMContentLoaded", function () {
        outdatedBrowser({
            bgColor: '#f25648',
            color: '#ffffff',
            lowerThan: 'flex'
        });
    });
</script>


    
    
<script src="https://cdn.jsdelivr.net/npm/mathjax@2.7.5/unpacked/MathJax.js?config=TeX-MML-AM_CHTML" defer></script>
<script>
document.addEventListener('DOMContentLoaded', function () {
    MathJax.Hub.Config({
        'HTML-CSS': {
            matchFontHeight: false
        },
        SVG: {
            matchFontHeight: false
        },
        CommonHTML: {
            matchFontHeight: false
        },
        tex2jax: {
            inlineMath: [
                ['$','$'],
                ['\\(','\\)']
            ]
        }
    });
});
</script>

    
    

<a id="back-to-top" title="Back to Top" href="javascript:;">
    <i class="fas fa-chevron-up"></i>
</a>
<script src="/js/back-to-top.js" defer></script>


    
    

    
    
    
    

    
    
    
    
    
    <script src="https://cdn.jsdelivr.net/npm/clipboard@2.0.4/dist/clipboard.min.js" defer></script>
    <script src="/js/clipboard.js" defer></script>
    

    
    
    

    


<script src="/js/main.js" defer></script>

    
    <div class="searchbox ins-search">
    <div class="searchbox-container ins-search-container">
        <div class="searchbox-input-wrapper">
            <input type="text" class="searchbox-input ins-search-input" placeholder="Type something..." />
            <span class="searchbox-close ins-close ins-selectable"><i class="fa fa-times-circle"></i></span>
        </div>
        <div class="searchbox-result-wrapper ins-section-wrapper">
            <div class="ins-section-container"></div>
        </div>
    </div>
</div>
<script>
    (function (window) {
        var INSIGHT_CONFIG = {
            TRANSLATION: {
                POSTS: 'Posts',
                PAGES: 'Pages',
                CATEGORIES: 'Categories',
                TAGS: 'Tags',
                UNTITLED: '(Untitled)',
            },
            CONTENT_URL: '/content.json',
        };
        window.INSIGHT_CONFIG = INSIGHT_CONFIG;
    })(window);
</script>
<script src="/js/insight.js" defer></script>
<link rel="stylesheet" href="/css/search.css">
<link rel="stylesheet" href="/css/insight.css">
    
</body>
</html>